SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Three utilities problem</title>

</head>

Three utilities problem

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"Water, gas and electricity" redirects here. For the utilities, see <a href="Public_utility" title="Public utility">Public utility</a>. For the novel Sewer, Gas & Electric, see <a href="Matt_Ruff" title="Matt Ruff">Matt Ruff</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner span:not(.skin-invert-image):not(.skin-invert):not(.bg-transparent) img{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:352px;max-width:352px"><div class="trow"><div class="tsingle" style="width:166px;max-width:166px"><div class="thumbimage" style="height:163px;overflow:hidden"></div></div><div class="tsingle" style="width:182px;max-width:182px"><div class="thumbimage" style="height:163px;overflow:hidden"></div></div></div><div class="trow" style="display:flex"><div class="thumbcaption">Two views of the utility graph, also known as the Thomsen graph or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"></div></div></div></div>

The three utilities problem, also known as water, gas and electricity, is a <a href="Mathematical_puzzle" title="Mathematical puzzle">mathematical puzzle</a> that asks for non-crossing connections to be drawn between three houses and three utility companies on a <a href="Plane_(geometry)" class="mw-redirect" title="Plane (geometry)">plane</a>. When posing it in the early 20th century, <a href="Henry_Dudeney" title="Henry Dudeney">Henry Dudeney</a> wrote that it was already an old problem. It is an <a href="List_of_impossible_puzzles" title="List of impossible puzzles">impossible puzzle</a>: it is not possible to connect all nine lines without any of them crossing. Versions of the problem on nonplanar surfaces such as a <a href="Torus" title="Torus">torus</a> or <a href="M%C3%B6bius_strip" title="Möbius strip">Möbius strip</a>, or that allow connections to pass through other houses or utilities, can be solved.

This puzzle can be formalized as a problem in <a href="Topological_graph_theory" title="Topological graph theory">topological graph theory</a> by asking whether the <a href="Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy">, with vertices representing the houses and utilities and edges representing their connections, has a <a href="Graph_embedding" title="Graph embedding">graph embedding</a> in the plane. The impossibility of the puzzle corresponds to the fact that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is not a <a href="Planar_graph" title="Planar graph">planar graph</a>. Multiple proofs of this impossibility are known, and form part of the proof of <a href="Kuratowski's_theorem" title="Kuratowski's theorem">Kuratowski's theorem</a> characterizing planar graphs by two forbidden subgraphs, one of which is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy">. The question of minimizing the <a href="Crossing_number_(graph_theory)" title="Crossing number (graph theory)">number of crossings</a> in drawings of complete bipartite graphs is known as <a href="Tur%C3%A1n's_brick_factory_problem" title="Turán's brick factory problem">Turán's brick factory problem</a>, and for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> the minimum number of crossings is one.

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is a graph with six vertices and nine edges, often referred to as the utility graph in reference to the problem.<a href="#cite_note-gs93-1">[1]</a> It has also been called the Thomsen graph after 19th-century chemist <a href="Hans_Peter_J%C3%B8rgen_Julius_Thomsen" title="Hans Peter Jørgen Julius Thomsen">Julius Thomsen</a>. It is a <a href="Well-covered_graph" title="Well-covered graph">well-covered graph</a>, the smallest <a href="Triangle-free_graph" title="Triangle-free graph">triangle-free</a> <a href="Cubic_graph" title="Cubic graph">cubic graph</a>, and the smallest non-planar <a href="Laman_graph" title="Laman graph">minimally rigid graph</a>.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

A review of the history of the three utilities problem is given by <a href="#CITEREFKullman1979">Kullman (1979)</a>. He states that most published references to the problem characterize it as "very ancient".<a href="#cite_note-kullman1979-2">[2]</a> In the earliest publication found by Kullman, <a href="Henry_Dudeney" title="Henry Dudeney">Henry Dudeney</a> (<a href="#CITEREFDudeney1917">1917</a>) names it "water, gas, and electricity". However, Dudeney states that the problem is "as old as the hills...much older than <a href="Electric_lighting" class="mw-redirect" title="Electric lighting">electric lighting</a>, or even <a href="Town_gas" class="mw-redirect" title="Town gas">gas</a>".<a href="#cite_note-dud17-3">[3]</a> Dudeney also published the same puzzle previously, in <a href="The_Strand_Magazine" title="The Strand Magazine">The Strand Magazine</a> in 1913.<a href="#cite_note-dud13-4">[4]</a> A competing claim of priority goes to <a href="Sam_Loyd" title="Sam Loyd">Sam Loyd</a>, who was quoted by his son in a posthumous biography as having published the problem in 1900.<a href="#cite_note-early-5">[5]</a>

Another early version of the problem involves connecting three houses to three wells.<a href="#cite_note-3wells-6">[6]</a> It is stated similarly to a different (and solvable) puzzle that also involves three houses and three fountains, with all three fountains and one house touching a rectangular wall; the puzzle again involves making non-crossing connections, but only between three designated pairs of houses and wells or fountains, as in modern <a href="Numberlink" title="Numberlink">numberlink</a> puzzles.<a href="#cite_note-fountains-7">[7]</a> Loyd's puzzle "The Quarrelsome Neighbors" similarly involves connecting three houses to three gates by three non-crossing paths (rather than nine as in the utilities problem); one house and the three gates are on the wall of a rectangular yard, which contains the other two houses within it.<a href="#cite_note-quarrelsome-8">[8]</a>

As well as in the three utilities problem, the graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> appears in late 19th-century and early 20th-century publications both in early studies of <a href="Structural_rigidity" title="Structural rigidity">structural rigidity</a><a href="#cite_note-dixon-9">[9]</a><a href="#cite_note-henneberg-10">[10]</a> and in <a href="Chemical_graph_theory" title="Chemical graph theory">chemical graph theory</a>, where <a href="Hans_Peter_J%C3%B8rgen_Julius_Thomsen" title="Hans Peter Jørgen Julius Thomsen">Julius Thomsen</a> proposed it in 1886 for the then-uncertain structure of <a href="Benzene" title="Benzene">benzene</a>.<a href="#cite_note-thomsen-11">[11]</a> In honor of Thomsen's work, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is sometimes called the Thomsen graph.<a href="#cite_note-bollobas-12">[12]</a>

<div class="mw-heading mw-heading2"><h2 id="Statement">Statement</h2></div>

The three utilities problem can be stated as follows:

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house to each company. Is there a way to make all nine connections without any of the lines crossing each other?</blockquote>

The problem is an abstract mathematical puzzle which imposes constraints that would not exist in a practical engineering situation. Its mathematical formalization is part of the field of <a href="Topological_graph_theory" title="Topological graph theory">topological graph theory</a> which studies the <a href="Embedding" title="Embedding">embedding</a> of <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graphs</a> on <a href="Surface_(topology)" title="Surface (topology)">surfaces</a>. An important part of the puzzle, but one that is often not stated explicitly in informal wordings of the puzzle, is that the houses, companies, and lines must all be placed on a two-dimensional surface with the topology of a <a href="Plane_(geometry)" class="mw-redirect" title="Plane (geometry)">plane</a>, and that the lines are not allowed to pass through other buildings; sometimes this is enforced by showing a drawing of the houses and companies, and asking for the connections to be drawn as lines on the same drawing.<a href="#cite_note-intuitive-13">[13]</a><a href="#cite_note-bona-14">[14]</a>

In more formal <a href="Graph_theory" title="Graph theory">graph-theoretic</a> terms, the problem asks whether the <a href="Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is a <a href="Planar_graph" title="Planar graph">planar graph</a>. This graph has six vertices in two subsets of three: one vertex for each house, and one for each utility. It has nine edges, one edge for each of the pairings of a house with a utility, or more abstractly one edge for each pair of a vertex in one subset and a vertex in the other subset. Planar graphs are the graphs that can be drawn without crossings in the plane, and if such a drawing could be found, it would solve the three utilities puzzle.<a href="#cite_note-intuitive-13">[13]</a><a href="#cite_note-bona-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Puzzle_solutions">Puzzle solutions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Unsolvability">Unsolvability</h3></div>

As it is usually presented (on a flat two-dimensional plane), the solution to the utility puzzle is "no": there is no way to make all nine connections without any of the lines crossing each other.

In other words, the graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is not planar. <a href="Kazimierz_Kuratowski" title="Kazimierz Kuratowski">Kazimierz Kuratowski</a> stated in 1930 that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is nonplanar,<a href="#cite_note-kuratowski-15">[15]</a> from which it follows that the problem has no solution. <a href="#CITEREFKullman1979">Kullman (1979)</a>, however, states that "Interestingly enough, Kuratowski did not publish a detailed proof that [ <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> ] is non-planar".<a href="#cite_note-kullman1979-2">[2]</a>

One proof of the impossibility of finding a planar embedding of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> uses a case analysis involving the <a href="Jordan_curve_theorem" title="Jordan curve theorem">Jordan curve theorem</a>.<a href="#cite_note-ayres-16">[16]</a> In this solution, one examines different possibilities for the locations of the vertices with respect to the 4-cycles of the graph and shows that they are all inconsistent with a planar embedding.<a href="#cite_note-trudeau-17">[17]</a>

Alternatively, it is possible to show that any <a href="Bridgeless_graph" class="mw-redirect" title="Bridgeless graph">bridgeless</a> <a href="Bipartite_graph" title="Bipartite graph">bipartite</a> planar graph with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> vertices and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> edges has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E\leq 2V-4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E\leq 2V-4}</annotation>

</semantics>

</math><img src="./70beb1e30e9814051cda351694ba0be2a3918b07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.827ex; height:2.343ex;" alt="{\displaystyle E\leq 2V-4}" loading="lazy"> by combining the <a href="Euler_characteristic" title="Euler characteristic">Euler formula</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V-E+F=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V-E+F=2}</annotation>

</semantics>

</math><img src="./759601e482258ff7a359a7db381abf60372c5b06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.245ex; height:2.343ex;" alt="{\displaystyle V-E+F=2}" loading="lazy"> (where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"> is the number of faces of a planar embedding) with the observation that the number of faces is at most half the number of edges (the vertices around each face must alternate between houses and utilities, so each face has at least four edges, and each edge belongs to exactly two faces). In the utility graph, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E=9}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E=9}</annotation>

</semantics>

</math><img src="./3e30b3725c69db66304ddbb037e87d7694fb2620.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.037ex; height:2.176ex;" alt="{\displaystyle E=9}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2V-4=8}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2V-4=8}</annotation>

</semantics>

</math><img src="./97e44529b628b5737cfa88cb3e9a98c57dc99cbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.213ex; height:2.343ex;" alt="{\displaystyle 2V-4=8}" loading="lazy"> so in the utility graph it is untrue that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E\leq 2V-4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E\leq 2V-4}</annotation>

</semantics>

</math><img src="./70beb1e30e9814051cda351694ba0be2a3918b07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:11.827ex; height:2.343ex;" alt="{\displaystyle E\leq 2V-4}" loading="lazy">. Because it does not satisfy this inequality, the utility graph cannot be planar.<a href="#cite_note-kappraff-18">[18]</a><div style="clear:left;" class=""></div>

<div class="mw-heading mw-heading3"><h3 id="Changing_the_rules">Changing the rules</h3></div>

<div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:471px;max-width:471px"><div class="trow"><div class="tsingle" style="width:155px;max-width:155px"><div class="thumbimage" style="height:115px;overflow:hidden"></div><div class="thumbcaption">Solution on a Möbius strip</div></div><div class="tsingle" style="width:155px;max-width:155px"><div class="thumbimage" style="height:115px;overflow:hidden"></div><div class="thumbcaption">Solution on a torus</div></div><div class="tsingle" style="width:155px;max-width:155px"><div class="thumbimage" style="height:115px;overflow:hidden"></div><div class="thumbcaption">A torus allows up to 4 utilities and 4 houses</div></div></div></div></div>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is a <a href="Toroidal_graph" title="Toroidal graph">toroidal graph</a>, which means that it can be embedded without crossings on a <a href="Torus" title="Torus">torus</a>, a surface of genus one.<a href="#cite_note-harary-19">[19]</a> These embeddings solve versions of the puzzle in which the houses and companies are drawn on a <a href="Coffee_mug" class="mw-redirect" title="Coffee mug">coffee mug</a> or other such surface instead of a flat plane.<a href="#cite_note-parker-20">[20]</a> There is even enough additional freedom on the torus to solve a version of the puzzle with four houses and four utilities.<a href="#cite_note-obeirne-21">[21]</a><a href="#cite_note-early-5">[5]</a> Similarly, if the three utilities puzzle is presented on a sheet of a transparent material, it may be solved after twisting and gluing the sheet to form a <a href="M%C3%B6bius_strip" title="Möbius strip">Möbius strip</a>.<a href="#cite_note-larsen-22">[22]</a>

Another way of changing the rules of the puzzle that would make it solvable, suggested by <a href="Henry_Dudeney" title="Henry Dudeney">Henry Dudeney</a>, is to allow utility lines to pass through other houses or utilities than the ones they connect.<a href="#cite_note-dud17-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Properties_of_the_utility_graph">Properties of the utility graph</h2></div>

Beyond the utility puzzle, the same graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> comes up in several other mathematical contexts, including <a href="Structural_rigidity" title="Structural rigidity">rigidity theory</a>, the classification of <a href="Cage_(graph_theory)" title="Cage (graph theory)">cages</a> and <a href="Well-covered_graph" title="Well-covered graph">well-covered graphs</a>, the study of <a href="Crossing_number_(graph_theory)" title="Crossing number (graph theory)">graph crossing numbers</a>, and the theory of <a href="Graph_minor" title="Graph minor">graph minors</a>.

<div class="mw-heading mw-heading3"><h3 id="Rigidity">Rigidity</h3></div>

The utility graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is a <a href="Laman_graph" title="Laman graph">Laman graph</a>, meaning that for <a href="Almost_all" title="Almost all">almost all</a> placements of its vertices in the plane, there is no way to continuously move its vertices while preserving all edge lengths, other than by a <a href="Rigid_transformation" title="Rigid transformation">rigid motion</a> of the whole plane, and that none of its <a href="Spanning_subgraph" class="mw-redirect" title="Spanning subgraph">spanning subgraphs</a> have the same <a href="Rigid_system" class="mw-redirect" title="Rigid system">rigidity</a> property. It is the smallest example of a nonplanar Laman graph.<a href="#cite_note-streinu-23">[23]</a> Despite being a minimally rigid graph, it has non-rigid embeddings with special placements for its vertices.<a href="#cite_note-dixon-9">[9]</a><a href="#cite_note-wh07-24">[24]</a> For general-position embeddings, a <a href="Polynomial_equation" class="mw-redirect" title="Polynomial equation">polynomial equation</a> describing all possible placements with the same edge lengths has degree 16, meaning that in general there can be at most 16 placements with the same lengths. It is possible to find systems of edge lengths for which up to eight of the solutions to this equation describe realizable placements.<a href="#cite_note-wh07-24">[24]</a>

<div class="mw-heading mw-heading3"><h3 id="Other_graph-theoretic_properties">Other graph-theoretic properties</h3></div>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is a <a href="Triangle-free_graph" title="Triangle-free graph">triangle-free graph</a>, in which every vertex has exactly three neighbors (a <a href="Cubic_graph" title="Cubic graph">cubic graph</a>). Among all such graphs, it is the smallest. Therefore, it is the <a href="Cage_(graph_theory)" title="Cage (graph theory)">(3,4)-cage</a>, the smallest graph that has three neighbors per vertex and in which the shortest cycle has length four.<a href="#cite_note-tutte-25">[25]</a>

Like all other <a href="Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graphs</a>, it is a <a href="Well-covered_graph" title="Well-covered graph">well-covered graph</a>, meaning that every <a href="Maximal_independent_set" title="Maximal independent set">maximal independent set</a> has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, and are of equal sizes. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is one of only seven <a href="Cubic_graph" title="Cubic graph">3-regular</a> <a href="K-vertex-connected_graph" title="K-vertex-connected graph">3-connected</a> well-covered graphs.<a href="#cite_note-cer93-26">[26]</a>

<div class="mw-heading mw-heading3"><h3 id="Generalizations">Generalizations</h3></div>

Two important characterizations of planar graphs, <a href="Kuratowski's_theorem" title="Kuratowski's theorem">Kuratowski's theorem</a> that the planar graphs are exactly the graphs that contain neither <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> nor the <a href="Complete_graph" title="Complete graph">complete graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{5}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{5}}</annotation>

</semantics>

</math><img src="./10a83da34fe45aa3be9a7d0b197417021bb4a884.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle K_{5}}" loading="lazy"> as a subdivision, and <a href="Wagner's_theorem" title="Wagner's theorem">Wagner's theorem</a> that the planar graphs are exactly the graphs that contain neither <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> nor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{5}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{5}}</annotation>

</semantics>

</math><img src="./10a83da34fe45aa3be9a7d0b197417021bb4a884.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle K_{5}}" loading="lazy"> as a <a href="Minor_(graph_theory)" class="mw-redirect" title="Minor (graph theory)">minor</a>, make use of and generalize the non-planarity of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy">.<a href="#cite_note-little-27">[27]</a>

<a href="P%C3%A1l_Tur%C3%A1n" title="Pál Turán">Pál Turán</a>'s "<a href="Tur%C3%A1n's_brick_factory_problem" title="Turán's brick factory problem">brick factory problem</a>" asks more generally for a formula for the <a href="Crossing_number_(graph_theory)" title="Crossing number (graph theory)">minimum number of crossings</a> in a drawing of the <a href="Complete_bipartite_graph" title="Complete bipartite graph">complete bipartite graph</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{a,b}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{a,b}}</annotation>

</semantics>

</math><img src="./1a9799e467ace40930d0c8e7f4928dfbbcb23200.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.238ex; height:2.843ex;" alt="{\displaystyle K_{a,b}}" loading="lazy"> in terms of the numbers of vertices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> on the two sides of the bipartition. The utility graph <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> may be drawn with only one crossing, but not with zero crossings, so its crossing number is one.<a href="#cite_note-early-5">[5]</a><a href="#cite_note-ps09-28">[28]</a><div style="clear:left;" class=""></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGriesSchneider1993" class="citation cs2"><a href="David_Gries" title="David Gries">Gries, David</a>; <a href="Fred_B._Schneider" title="Fred B. Schneider">Schneider, Fred B.</a> (1993), "Chapter 19: A theory of graphs", A Logical Approach to Discrete Math, New York: Springer, pp. 423–460, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4757-3837-7">10.1007/978-1-4757-3837-7</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4419-2835-1</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:206657798">206657798</a></cite>. See p. 437: "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> is known as the utility graph".

</li>

<li id="cite_note-kullman1979-2">^ <a href="#cite_ref-kullman1979_2-0">a</a> <a href="#cite_ref-kullman1979_2-1">b</a> <cite id="CITEREFKullman1979" class="citation cs2">Kullman, David (1979), "The utilities problem", <a href="Mathematics_Magazine" title="Mathematics Magazine">Mathematics Magazine</a>, 52 (5): 299–302, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F0025570X.1979.11976807">10.1080/0025570X.1979.11976807</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2689782">2689782</a></cite>

</li>

<li id="cite_note-dud17-3">^ <a href="#cite_ref-dud17_3-0">a</a> <a href="#cite_ref-dud17_3-1">b</a> <cite id="CITEREFDudeney1917" class="citation cs2"><a href="Henry_Dudeney" title="Henry Dudeney">Dudeney, Henry</a> (1917), <a rel="nofollow" class="external text" href="https://archive.org/stream/amusementsinmath00dude#page/72">"Problem 251 – Water, Gas, and Electricity"</a>, Amusements in mathematics, vol. 100, Thomas Nelson, p. 73, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1917Natur.100..302.">1917Natur.100..302.</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2F100302a0">10.1038/100302a0</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10245524">10245524</a></cite>. The solution given on <a rel="nofollow" class="external text" href="https://archive.org/details/amusementsinmath00dude/page/200">pp. 200–201</a> involves passing a line through one of the other houses.

</li>

<li id="cite_note-dud13-4"><a href="#cite_ref-dud13_4-0">^</a> <cite id="CITEREFDudeney1913" class="citation cs2"><a href="Henry_Dudeney" title="Henry Dudeney">Dudeney, Henry</a> (1913), <a rel="nofollow" class="external text" href="https://archive.org/stream/TheStrandMagazineAnIllustratedMonthly/TheStrandMagazine1913bVol.XlviJul-dec#page/n119/mode/2up">"Perplexities, with some easy puzzles for beginners"</a>, <a href="The_Strand_Magazine" title="The Strand Magazine">The Strand Magazine</a>, vol. 46, p. 110</cite>

</li>

<li id="cite_note-early-5">^ <a href="#cite_ref-early_5-0">a</a> <a href="#cite_ref-early_5-1">b</a> <a href="#cite_ref-early_5-2">c</a> <cite id="CITEREFBeinekeWilson2010" class="citation cs2"><a href="L._W._Beineke" title="L. W. Beineke">Beineke, Lowell</a>; <a href="Robin_Wilson_(mathematician)" title="Robin Wilson (mathematician)">Wilson, Robin</a> (2010), "The early history of the brick factory problem", <a href="The_Mathematical_Intelligencer" title="The Mathematical Intelligencer">The Mathematical Intelligencer</a>, 32 (2): 41–48, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00283-009-9120-4">10.1007/s00283-009-9120-4</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2657999">2657999</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122588849">122588849</a></cite>

</li>

<li id="cite_note-3wells-6"><a href="#cite_ref-3wells_6-0">^</a> <cite class="citation cs2"><a rel="nofollow" class="external text" href="https://books.google.com/books?id=yLSTwH0pINIC&q=%22three+houses+and+three+wells%22">"Puzzle"</a>, Successful Farming, vol. 13, p. 50, 1914</cite>; <cite class="citation cs2"><a rel="nofollow" class="external text" href="https://books.google.com/books?id=w8tPAQAAMAAJ&pg=PA392">"A well and house puzzle"</a>, The Youth's Companion, vol. 90, no. 2, p. 392, 1916</cite>.

</li>

<li id="cite_note-fountains-7"><a href="#cite_ref-fountains_7-0">^</a> <cite class="citation cs2"><a rel="nofollow" class="external text" href="https://books.google.com/books?id=kbI_AQAAMAAJ&pg=PA276">"32. The fountain puzzle"</a>, The Magician's Own Book, Or, The Whole Art of Conjuring, New York: Dick & Fitzgerald, 1857, p. 276</cite>

</li>

<li id="cite_note-quarrelsome-8"><a href="#cite_ref-quarrelsome_8-0">^</a> <cite id="CITEREFLoyd1959" class="citation cs2"><a href="Sam_Loyd" title="Sam Loyd">Loyd, Sam</a> (1959), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=QCy6DzgqcI4C&pg=PA79">"82: The Quarrelsome Neighbors"</a>, in <a href="Martin_Gardner" title="Martin Gardner">Gardner, Martin</a> (ed.), Mathematical Puzzles of Sam Loyd, Dover Books, p. 79, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780486204987</bdi></cite><code class="cs1-code">{{citation}}</code>: CS1 maint: ignored ISBN errors (link)

</li>

<li id="cite_note-dixon-9">^ <a href="#cite_ref-dixon_9-0">a</a> <a href="#cite_ref-dixon_9-1">b</a> <cite id="CITEREFDixon1899" class="citation cs2"><a href="Alfred_Cardew_Dixon" title="Alfred Cardew Dixon">Dixon, A. C.</a> (1899), <a rel="nofollow" class="external text" href="https://gdz.sub.uni-goettingen.de/id/PPN599484047_0029?tify=%7B%22pages%22%3A%5B5%5D%7D">"On certain deformable frameworks"</a>, <a href="Messenger_of_Mathematics" title="Messenger of Mathematics">Messenger of Mathematics</a>, 29: 1–21, <a href="JFM_(identifier)" class="mw-redirect" title="JFM (identifier)">JFM</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:30.0622.02">30.0622.02</a></cite>

</li>

<li id="cite_note-henneberg-10"><a href="#cite_ref-henneberg_10-0">^</a> <cite id="CITEREFHenneberg1908" class="citation cs2">Henneberg, L. (1908), <a rel="nofollow" class="external text" href="https://archive.org/details/encyklomath104encyrich/page/n367">"Die graphische Statik der starren Körper"</a>, Encyklopädie der Mathematischen Wissenschaften, vol. 4, pp. 345–434</cite>. See in particular <a rel="nofollow" class="external text" href="https://archive.org/stream/encyklomath104encyrich/#page/n425">p. 403</a>.

</li>

<li id="cite_note-thomsen-11"><a href="#cite_ref-thomsen_11-0">^</a> <cite id="CITEREFThomsen1886" class="citation cs2"><a href="Hans_Peter_J%C3%B8rgen_Julius_Thomsen" title="Hans Peter Jørgen Julius Thomsen">Thomsen, Julius</a> (July 1886), <a rel="nofollow" class="external text" href="https://archive.org/download/crossref-pre-1909-scholarly-works/10.1002%252Fcber.18860190141.zip/10.1002%252Fcber.188601902285.pdf">"Die Constitution des Benzols"</a> (PDF), Berichte der Deutschen Chemischen Gesellschaft, 19 (2): 2944–2950, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fcber.188601902285">10.1002/cber.188601902285</a></cite>

</li>

<li id="cite_note-bollobas-12"><a href="#cite_ref-bollobas_12-0">^</a> <cite id="CITEREFBollobás1998" class="citation cs2"><a href="B%C3%A9la_Bollob%C3%A1s" title="Béla Bollobás">Bollobás, Béla</a> (1998), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA23">Modern Graph Theory</a>, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, p. 23, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4612-0619-4">10.1007/978-1-4612-0619-4</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-98488-7</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1633290">1633290</a></cite>

</li>

<li id="cite_note-intuitive-13">^ <a href="#cite_ref-intuitive_13-0">a</a> <a href="#cite_ref-intuitive_13-1">b</a> <cite id="CITEREFHarary1960" class="citation cs2"><a href="Frank_Harary" title="Frank Harary">Harary, Frank</a> (1960), "Some historical and intuitive aspects of graph theory", <a href="SIAM_Review" class="mw-redirect" title="SIAM Review">SIAM Review</a>, 2 (2): 123–131, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1960SIAMR...2..123H">1960SIAMR...2..123H</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1002023">10.1137/1002023</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0111698">0111698</a></cite>

</li>

<li id="cite_note-bona-14">^ <a href="#cite_ref-bona_14-0">a</a> <a href="#cite_ref-bona_14-1">b</a> <cite id="CITEREFBóna2011" class="citation cs2"><a href="Mikl%C3%B3s_B%C3%B3na" title="Miklós Bóna">Bóna, Miklós</a> (2011), A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific, pp. 275–277, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9789814335232</bdi></cite>. Bóna introduces the puzzle (in the form of three houses to be connected to three wells) on p. 275, and writes on p. 277 that it "is equivalent to the problem of drawing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy"> on a plane surface without crossings".

</li>

<li id="cite_note-kuratowski-15"><a href="#cite_ref-kuratowski_15-0">^</a> <cite id="CITEREFKuratowski1930" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Kazimierz_Kuratowski" title="Kazimierz Kuratowski">Kuratowski, Kazimierz</a> (1930), <a rel="nofollow" class="external text" href="http://matwbn.icm.edu.pl/ksiazki/fm/fm15/fm15126.pdf">"Sur le problème des courbes gauches en topologie"</a> (PDF), Fundamenta Mathematicae (in French), 15: 271–283, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4064%2Ffm-15-1-271-283">10.4064/fm-15-1-271-283</a></cite>

</li>

<li id="cite_note-ayres-16"><a href="#cite_ref-ayres_16-0">^</a> <cite id="CITEREFAyres1938" class="citation cs2">Ayres, W. L. (1938), "Some elementary aspects of topology", <a href="The_American_Mathematical_Monthly" title="The American Mathematical Monthly">The American Mathematical Monthly</a>, 45 (2): 88–92, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F00029890.1938.11990773">10.1080/00029890.1938.11990773</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2304276">2304276</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1524194">1524194</a></cite>

</li>

<li id="cite_note-trudeau-17"><a href="#cite_ref-trudeau_17-0">^</a> <cite id="CITEREFTrudeau1993" class="citation cs2">Trudeau, Richard J. (1993), Introduction to Graph Theory, Dover Books on Mathematics, New York: Dover Publications, pp. 68–70, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-486-67870-2</bdi></cite>

</li>

<li id="cite_note-kappraff-18"><a href="#cite_ref-kappraff_18-0">^</a> <cite id="CITEREFKappraff2001" class="citation cs2"><a href="Jay_Kappraff" title="Jay Kappraff">Kappraff, Jay</a> (2001), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=twF7pOYXSTcC&pg=PA128">Connections: The Geometric Bridge Between Art and Science</a>, K & E Series on Knots and Everything, vol. 25, World Scientific, p. 128, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9789810245863</bdi></cite>

</li>

<li id="cite_note-harary-19"><a href="#cite_ref-harary_19-0">^</a> <cite id="CITEREFHarary1964" class="citation cs2"><a href="Frank_Harary" title="Frank Harary">Harary, F.</a> (1964), "Recent results in topological graph theory", Acta Mathematica, 15 (3–4): 405–411, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01897149">10.1007/BF01897149</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2027.42%2F41775">2027.42/41775</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0166775">0166775</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:123170864">123170864</a></cite>; see p. 409.

</li>

<li id="cite_note-parker-20"><a href="#cite_ref-parker_20-0">^</a> <cite id="CITEREFParker2015" class="citation cs2"><a href="Matt_Parker" title="Matt Parker">Parker, Matt</a> (2015), Things to Make and Do in the Fourth Dimension: A Mathematician's Journey Through Narcissistic Numbers, Optimal Dating Algorithms, at Least Two Kinds of Infinity, and More, New York: Farrar, Straus and Giroux, pp. 180–181, 191–192, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-374-53563-6</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3753642">3753642</a></cite>

</li>

<li id="cite_note-obeirne-21"><a href="#cite_ref-obeirne_21-0">^</a> <cite id="CITEREFO’Beirne1961" class="citation cs2">O’Beirne, T. H. (December 21, 1961), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=rykw9gx81GoC&pg=PA751">"Christmas puzzles and paradoxes, 51: For boys, men and heroes"</a>, <a href="New_Scientist" title="New Scientist">New Scientist</a>, vol. 12, no. 266, pp. 751–753</cite>

</li>

<li id="cite_note-larsen-22"><a href="#cite_ref-larsen_22-0">^</a> <cite id="CITEREFLarsen1994" class="citation cs2">Larsen, Mogens Esrom (1994), "Misunderstanding my mazy mazes may make me miserable", in <a href="Richard_K._Guy" title="Richard K. Guy">Guy, Richard K.</a>; Woodrow, Robert E. (eds.), Proceedings of the Eugène Strens Memorial Conference on Recreational Mathematics and its History held at the University of Calgary, Calgary, Alberta, August 1986, MAA Spectrum, Washington, DC: Mathematical Association of America, pp. 289–293, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-88385-516-X</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1303141">1303141</a></cite>. See <a rel="nofollow" class="external text" href="https://books.google.com/books?id=FsH2DwAAQBAJ&pg=PA292">Figure 7, p. 292</a>.

</li>

<li id="cite_note-streinu-23"><a href="#cite_ref-streinu_23-0">^</a> <cite id="CITEREFStreinu2005" class="citation cs2"><a href="Ileana_Streinu" title="Ileana Streinu">Streinu, Ileana</a> (2005), "Pseudo-triangulations, rigidity and motion planning", <a href="Discrete_%26_Computational_Geometry" title="Discrete & Computational Geometry">Discrete & Computational Geometry</a>, 34 (4): 587–635, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00454-005-1184-0">10.1007/s00454-005-1184-0</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2173930">2173930</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:25281202">25281202</a></cite>. See p. 600: "Not all generically minimally rigid graphs have embeddings as pseudo-triangulations, because not all are planar graphs. The smallest example is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{3,3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{3,3}}</annotation>

</semantics>

</math><img src="./eb683d61b6b89e9e408ac8488e97d892e1776fa8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.307ex; height:2.843ex;" alt="{\displaystyle K_{3,3}}" loading="lazy">".

</li>

<li id="cite_note-wh07-24">^ <a href="#cite_ref-wh07_24-0">a</a> <a href="#cite_ref-wh07_24-1">b</a> <cite id="CITEREFWalterHusty2007" class="citation cs2">Walter, D.; Husty, M. L. (2007), <a rel="nofollow" class="external text" href="https://geometrie.uibk.ac.at/obsolete/institutsangehoerige/husty/dld/A681.pdf">"On a nine-bar linkage, its possible configurations and conditions for paradoxical mobility"</a> (PDF), in Merlet, Jean-Pierre; Dahan, Marc (eds.), 12th World Congress on Mechanism and Machine Science (IFToMM 2007), <a href="International_Federation_for_the_Promotion_of_Mechanism_and_Machine_Science" title="International Federation for the Promotion of Mechanism and Machine Science">International Federation for the Promotion of Mechanism and Machine Science</a></cite>

</li>

<li id="cite_note-tutte-25"><a href="#cite_ref-tutte_25-0">^</a> <cite id="CITEREFTutte1947" class="citation cs2"><a href="W._T._Tutte" title="W. T. Tutte">Tutte, W. T.</a> (1947), "A family of cubical graphs", <a href="Proceedings_of_the_Cambridge_Philosophical_Society" class="mw-redirect" title="Proceedings of the Cambridge Philosophical Society">Proceedings of the Cambridge Philosophical Society</a>, 43 (4): 459–474, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1947PCPS...43..459T">1947PCPS...43..459T</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2Fs0305004100023720">10.1017/s0305004100023720</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0021678">0021678</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:123505185">123505185</a></cite>

</li>

<li id="cite_note-cer93-26"><a href="#cite_ref-cer93_26-0">^</a> <cite id="CITEREFCampbellEllinghamRoyle1993" class="citation cs2">Campbell, S. R.; <a href="Mark_Ellingham" title="Mark Ellingham">Ellingham, M. N.</a>; <a href="Gordon_Royle" title="Gordon Royle">Royle, Gordon F.</a> (1993), "A characterisation of well-covered cubic graphs", Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1220613">1220613</a></cite>

</li>

<li id="cite_note-little-27"><a href="#cite_ref-little_27-0">^</a> <cite id="CITEREFLittle1976" class="citation cs2">Little, Charles H. C. (1976), "A theorem on planar graphs", in Casse, Louis R. A.; Wallis, Walter D. (eds.), Combinatorial Mathematics IV: Proceedings of the Fourth Australian Conference Held at the University of Adelaide August 27–29, 1975, Lecture Notes in Mathematics, vol. 560, Springer, pp. 136–141, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0097375">10.1007/BFb0097375</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-08053-4</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0427121">0427121</a></cite>

</li>

<li id="cite_note-ps09-28"><a href="#cite_ref-ps09_28-0">^</a> <cite id="CITEREFPachSharir2009" class="citation cs2"><a href="J%C3%A1nos_Pach" title="János Pach">Pach, János</a>; <a href="Micha_Sharir" title="Micha Sharir">Sharir, Micha</a> (2009), "5.1 Crossings—the Brick Factory Problem", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, <a href="American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a>, pp. 126–127</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cut-the-knot.org/do_you_know/3Utilities.shtml">3 Utilities Puzzle</a> at <a href="Cut-the-knot" class="mw-redirect" title="Cut-the-knot">Cut-the-knot</a></li>

<li><a rel="nofollow" class="external text" href="http://www.archimedes-lab.org/How_to_Solve/Water_gas.html">The Utilities Puzzle</a> explained and "solved" at <a href="Archimedes-lab.org" title="Archimedes-lab.org">Archimedes-lab.org</a></li>

<li><cite id="CITEREFWeisstein" class="citation web cs2"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a>, <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/UtilityGraph.html">"Utility graph"</a>, <a href="MathWorld" title="MathWorld">MathWorld</a></cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-25" href="https://en.wikipedia.org/wiki/?title=Three_utilities_problem&oldid=1297374448">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>